package q25_reverseKGroup;

import static CommonClass.Common.*;

public class Solution {
    public static void main(String[] args) {
        ListNode testNode = generateList(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10});

        printList(reverseKGroup(testNode, 1));
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode startNode = new ListNode(0);
        startNode.next = head;
        // 初始设定
        ListNode pre = startNode;
        ListNode end = startNode;
        /*
        循环条件：
        在每次循环之后，都会重置end以及pre的位置，所以当它next已经为空时，则可以停止
         */
        while (end.next != null) {
            // 首先将end放到需要反转k长度的链表的末尾 假设0是startNode（额外设定的node） 且k = 3
            // 那么对于一个0 1 2 3 4 5 。。。 的链表 end应该被送到3的位置
            for (int i = 0; (i < k) && (end != null); i++) {
                end = end.next;
            }
            // 如果end经过数次next指定，如果k次以内变为null，则说明反转数量不足，结束翻转。
            if (end == null) {
                break;
            }
            // 反转流程；首先将nex指定到end的next位置，因为此后需要断开链表，所以要保存end.next
            // start自然就是翻转开始的地方
            ListNode nex = end.next;
            ListNode start = pre.next;
            // 断开
            end.next = null;
            // 把pre的next指到翻转后的一个链表
            pre.next = reverseSpNode(start);
            // 值得注意的是，这个时候start并不是按照我们所想的直接变成了一个末尾且**孤立**的节点
            // 因此还是可以利用start来继续连接到下一个nex的位置
            start.next = nex;
            // 重新将end和pre指定到下一个翻转链表的**前一个**的位置
            end = start;
            pre = start;
        }

        return startNode.next;
    }

    /**
     * 翻转整个链表的函数
     */
    public static ListNode reverseSpNode(ListNode head) {

        if ((head == null) || (head.next == null)) {
            return head;
        }
        // 设置一个哑节点，用来连接要反转的链表的头节点
        ListNode StarNode = new ListNode(0);
        ListNode temp = head;
        while (temp.next != null) {
            ListNode b = temp.next;
            temp.next = b.next;
            b.next = StarNode.next;
            StarNode.next = b;
        }
        return StarNode.next;
    }


}
